package com.mamingchao.basic.heap;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created by mlamp on 2024/5/23.
 * * 已知一个几乎有序的数组。几乎有序，是指如果把数组排好顺序，每个元素的移动距离一定不超过K步，并且K相对于数组长度来讲是比较小的
 * 请选择一个合适的排序测列，对这个数组进行排序
 *
 * 举个例子，比如 K==5
 * [            ]
 * 0 1 2 3 4 5 6
 * 从0到5的元素，视为一个堆结构，调整顺序为一个最小堆；调整之后，0位置的数据即为 0~5之间最小的，也是整个数组最小的；
 * 因为如果 index == 6位置的数据，比前五 都小，就不满足 题干所述，【把整个排好序，每个元素的移动距离不超过K步】
 * 把 1~6位置的元素视为一个堆结构，调整顺序为最小堆；调整之后，1位置即为 1~6之间的最小值，也是整个数组除了0位置之外所有元素的最小值
 * 周而复始，最终得到一个排好顺序的
 *
 * [2,3,1,6,4,9,8,5]
 *  0 1 2 3 4 5 6 7
 *  ^       ^
 *fistIndex secondIndex
 *
 * 这个是左老师的讲解的答案，k的窗口使用了两个 index来实现；很巧妙，所以写下来 记录下
 */
public class HeapSortIssue1_2 {
    private static void sortArrDistanceLessK(int[] arr, int k){
        // 使用底层使用小根堆实现的 优先级队列
        PriorityQueue<Integer> minRootValueHeap = new PriorityQueue<>();

        int secondIndex = 0;
        // 先把前 k个(数组长度小于k，就一次性都放进去) 放到小根堆里面
        for (; secondIndex < Math.min(arr.length, k); secondIndex++) {
            minRootValueHeap.add(arr[secondIndex]);
        }

        int firstIndex = 0;
        for (; secondIndex < arr.length; firstIndex++,secondIndex++) {
            arr[firstIndex] = minRootValueHeap.poll();
            minRootValueHeap.add(arr[secondIndex]);
        }

        while (!minRootValueHeap.isEmpty()){
            arr[firstIndex++] = minRootValueHeap.poll();
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,3,1,6,4,9,8,5};
        final int k = 5;

        sortArrDistanceLessK(arr, k);

        System.out.println(Arrays.toString(arr));
    }
}
